package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/2-keys-keyboard/">
 * 650. 只有两个键的键盘</a>
 *
 * @author or2
 * @Description 最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
 * Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
 * Paste（粘贴）：粘贴 上一次 复制的字符。
 * 给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
 * @create 2021年09月19日 时间: 16:51
 */
public class No650 {
    /**
     * <span color="yellow">参考</span> - <a href="https://leetcode-cn.com/u/ac_oier/">宫水三叶</a>
     * <p>动态规划表现很差 - 转换成业务, 用数学的方式进行处理
     * @param n 字符串长度
     * @return 最少操作次数
     */
    public int minSteps(int n) {
        int ans = 0;
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                ans += i;
                n /= i;
            }
        }
        if (n != 1) ans += n;
        return ans;
    }
}
